package com.fr.lintcode;

import org.junit.Test;

/**
*作者：furong
*日期：2017年1月22日
*时间：下午6:13:12
*/
public class Q92 {
    /**
     * @param m: An integer m denotes the size of a backpack
     * @param A: Given n items with size A[i]
     * @return: The maximum size
     */
    public int backPack(int m, int[] A) {
        if (m <= 0 || A == null || A.length <= 0) {
            return 0;
        }
        int length = A.length;
        int weight[][] = new int[length + 1][m + 1];
        for (int i = 1; i <= length; i++) {
            for (int j = 1; j <= m; j++) {
                if (j < A[i - 1]) {
                    weight[i][j] = weight[i - 1][j];
                } else {
                    weight[i][j] = Math.max(weight[i - 1][j], weight[i - 1][j - A[i - 1]] + A[i - 1]);
                }
            }
        }
        return weight[length][m];
    }

    @Test
    public void testA() {
        int m = 5;
        int A[] = { 2, 3, 5, 7 };
        System.out.println(backPack(m, A));

    }
}
